LeetCode——电话号码的字母组合

NO.17 电话号码的字母组合中等

思路一：回溯法 如果这道题加一个条件：“每次输入3位字符的字符串”。那么这道题就非常简单了，直接三层for循环就解决了。这道题棘手的地方就是如何确定循环的层数，这时候递归就派上用场了（模仿大佬的语气）！

例如输入”2345”这样的字符串：第一次递归处理2，然后处理完第一个字符2之后，将输入的字符改变成”345”并调用第二个递归函数；第二次递归处理3，将字符串改变成”45”后再次递归；第三次递归处理4，将字符串改变成 “5”后继续递归；第四次递归处理5，将字符串改变成””后继续递归；最后发现字符串为空了，将结果放到列表中并返回。

上面是从函数调用的角度去看的，而每次调用下一层递归时，都需要将本层的一些处理结果放到一个临时变量中，再传递给下一层，从这个变量层层传递的变化看，就像一棵树一样，这个算法的时间复杂度很高，是O(3^n)这个级别的。

//    用数组或hashmap存储数字及其对应的字符表
    String[] letters={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//    结果集
    List<String> result=new ArrayList<>();

    public List<String> letterCombinations(String digits) {
//        边界处理
        if (digits.length()==0||digits==null)return result;
        backTrack(digits,"",0);
        return result;
    }

//    递归函数
    public void backTrack(String str,String combination,int index){
//        递归终止条件，当index==str.length()时说明str==""
        if (index==str.length()){
            result.add(combination);
            return;
        }
//        获取当前index位置的字符，此处和前文的思路中有所不同：没有采用每次将字符串切割的方法
//        subString()每次都会生成新的字符串，而用index方式取当前第一个字符，效率更高一点
        char c= str.charAt(index);
        String letter=letters[c-'0'];
//        遍历letter字符串，例如第一次得到的是‘2’，即遍历“abc”
        for (int i=0;i<letter.length();i++){
//            这里是比较值得思考的地方，递归调用
            backTrack(str,combination+letter.charAt(i),index+1);
        }
    }

时间复杂度：O(3^n)

思路二：队列法 利用队列先进先出的特点来处理该问题。

直接用一个例子来说明思路：假设输入的还是”23”,先将”2”对应的字符依次放入队列，队列res变为{“a”,”b”,”c”}；将此时队列中的每个字符串依次取出的同时分别和下一个输入数字所对应的字符拼接后重新放入队列，将”a”取出和第二个输入数字”3”对应的字符”def”依次拼接后重新放入队列，队列res变为{“b”,”c”,”ad”,”ae”,”af”}，将”b”取出和第二个输入数字”3”对应的字符”def”依次拼接后重新放入队列，队列res变为{“c”,”ad”,”ae”,”af”,”bd”,”be”,”bf”}，将”c”取出和第二个输入数字”3”对应的字符”def”依次拼接后重新放入队列，队列res变为{“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”}；所有输入数字遍历结束。

public List<String> letterCombinations(String digits) {
        List<String> res=new ArrayList<>();
//        边界处理
        if (digits==null||digits.length()==0)return res;
//        用数组或hashmap存储数字及其对应的字符表
        String[] letters={"","#","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//        先往队列中加入一个空字符，防止第一次循环从队列中取出第一个元素时出现下标越界异常
        res.add("");
//        遍历输入的字符串
        for(int i=0;i<digits.length();i++){
//            取出当前遍历数字对应的字符串
            String letter=letters[digits.charAt(i)-'0'];
//            获取当前队列的长度，不能在for循环中直接j<res.size()，因为内层循环中队列在不断增长，导致死循环
            int size = res.size();
//            遍历队列中每个元素
            for (int j=0;j<size;j++){
//                从队列中取出第一个元素
                String temp = res.remove(0);
//                遍历当前数字对应的字符串的每个字符，依次和取出的第一个元素拼接后重新放入队列
                for (int k=0;k<letter.length();k++){
                    res.add(temp+letter.charAt(k));
                }
            }
        }
        return res;
    }

时间复杂度：O(3^n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.17 电话号码的字母组合 中等

NO.17 电话号码的字母组合中等